Quantization is the process of converting input values into discrete values in accordance with some fidelity criterion. A typical example of quantization is the conversion of a continuous amplitude signal into discrete amplitude values. The signal is first sampled, then quantized.
For quantization, a range of expected values of the input signal is divided into a series of subranges. Each subrange has an associated quantization level. For example, for quantization to 8-bit values, there would be 256 levels. A sample value of the input signal that is within a certain subrange is converted to the associated quantizing level. For example, for 8-bit quantization, a sample of the input signal would be converted to one of 256 levels, each level represented by an 8-bit value.
Vector quantization is a method of quantization, which is based on the linear and non-linear correlation between samples and the shape of the probability distribution. Essentially, vector quantization is a lookup process, where the lookup table is referred to as a "codebook". The codebook lists each quantization level, and each level has an associated "code-vector". The vector quantization process compares an input vector to the code-vectors and determines the best code-vector in terms of minimum distortion. Where x is the input vector, the comparison of distortion values may be expressed as: EQU d(x, y.sup.(j)).ltoreq.d(x, y.sup.(k))
, for all j not equal to k. The codebook is represented by y.sup.(j), where y.sup.(j) is the jth code-vector, 0.ltoreq.j.ltoreq.L, and L is the number of levels in the codebook.
Multi-stage vector quantization is a type of vector quantization. This process obtains a central quantized vector (the output vector) by adding a number of quantized vectors. The output vector is sometimes referred to as a "reconstructed" vector. Each vector used in the reconstruction is from a different codebook, each codebook corresponding to a "stage" of the quantization process. Each codebook is designed especially for a stage of the search. An input vector is quantized with the first codebook, and that value is quantized with the second codebook, etc. The set of vectors used in the reconstruction may be expressed as: EQU y.sup.(j.sbsp.0.sup., j.sbsp.1.sup., . . . j.sbsp.S-1.sup.) =y.sub.0.sup.(j.sbsp.0.sup.) +y.sub.1.sup.(j.sbsp.1.sup.) +y.sub.S-1.sup.(j.sbsp.S-1.sup.)
, where S is the number of stages and y.sub.s is the codebook for the sth stage. For example, for a three-dimensional input vector, such as x=(2,3,4), the reconstruction vectors for a two-stage search might be y.sub.0 =(1,2,3) and y.sub.1 =(1,1,1) (a perfect quantization and not always the case).
During multi-stage vector quantization, the codebooks may be searched using a sub-optimal tree search algorithm, also known as an M-algorithm. At each stage, M number of "best" code-vectors are passed from one stage to the next. The "best" code-vectors are selected in terms of minimum distortion. The search continues until the final stage, when only one best code-vector is determined.